package com.sise.Str;

/**
 *      28. 实现 strStr()
 *
 *      实现 strStr()函数。
 *      给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
 *      当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *      对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
 *
 *      输入：haystack = "hello", needle = "ll"
 *      输出：2
 *
 *      题解：
 *      1、先看视频 https://www.bilibili.com/video/BV1iJ411a7Kb?from=search&seid=3148493841781911757
 *      2、再看 leetcode 讲解：https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
 */
public class _28_strStr {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;

        int longStrLength = haystack.length();         // 原串
        int patternLength = needle.length();           // 匹配串

        haystack = " " + haystack;                     // 空格（哨兵）。目的是让 j 下标从 0 开始，省去 j 从 -1 开始的麻烦。
        needle = " " + needle;

        char[] longStrChars = haystack.toCharArray();
        char[] patternChars = needle.toCharArray();

        /**
         *  构建 next[] 数组，这里的 i，j 是同时初始化的，而 i = 2 是因为在字符串最前面添加了 “ ” 空字符串，同时 i，j 需要错开一位(可看哔哩哔哩视频理解) 才可以进行对比形成 next[],
         *  1、首先判断当前位置的 i、j 元素是否相等，如果不相等，那么取当前 next[j] 位置的值 赋值给 j，因为存在相同前后缀的原因，所以我们可以从 j = next[j] 的位置重新匹配，
         *      这样子就可以省去相同前后缀的步数了。例如：
         *      原串： a b e a b a | b e a b f
         *    匹配串： a b e a b f
         *    可以看到此时 a 和 f 不匹配，那么此时 匹配串 存在 "a b" 的相同前后缀，故此我们可以省去 "a b" 这两步，也就是 next[j] = 2 的大小，
         *    故此从 匹配串 的第三位开始(从相同前缀的下一个位置开始匹配)， e 开始往后推算，但此时依旧不相等，那么就继续 while 循环
         *
         *  2、如果匹配相等，那么就将 j++，而 i 不用动，因为在 for 循环中，就已经有 i++
         *  3、经过上面的匹配，只有两种可能，而这两种可能都已经处理。所以最后将 j 的数值赋给 next[i]，代表此位置有 j 个相同的前后缀
         *
         *  意义： next[j] 的数值就是 当前位置有 j 个相同前后缀
         */
        int[] next = new int[patternLength + 1];        // 构建 next 数组，数组长度为匹配串的长度(next 数组是和匹配串相关的)
        for (int i = 2, j = 0; i <= patternLength; i++) {   // 构建过程 i = 2，j = 0开始， i 小于等于匹配串长度【0:空字符串，1:只有一个，无须比较 2:起始点】
            while (j > 0 && patternChars[i] != patternChars[j + 1])     // 如果匹配不成功，j = next(j)
                j = next[j];
            if (patternChars[i] == patternChars[j + 1]) // 匹配成功的话，先让 j++
                j++;
            next[i] = j;                                // 更新 next[i]，结束本次循环，i++
        }

        /**
         *  前面是为了构建 next[]，这里才是真正的解答，但这里的操作和前面相似
         *
         *  对比字符串，如果不相等，那么就看 next[] 数组中的前后缀 j = next[j]，并且从前后缀的 j + 1 位置开始往后推算，
         *  直到 j == patterLength 的长度，那么就说明匹配成功，返回此时 i 减去匹配串长度的数值，否则就返回 -1
         */
        for (int i = 1, j = 0; i <= longStrLength; i++) {       // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度【匹配 i 从 1 开始】
            while (j > 0 && longStrChars[i] != patternChars[j + 1])     // 匹配不成功 j = next(j)
                j = next[j];
            if (longStrChars[i] == patternChars[j + 1]) j++;            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (j == patternLength) return i - patternLength;           // 整一段匹配成功，直接返回下标
        }
        return -1;
    }
}
